package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 归并排序 利用最经典的分治策略（分治将问题分成一些小的问题然后递归求解）
 * 先分
 * 再合
 *
 * 1）将所有元素拆分成一个一个（多次拆分）
 * 2）然后进行合并
 * 2.1）两个单独的合并成一个包含两个元素的有序队列。
 * 2.2）然后两个包含两个元素的有序队列再进行合并。
 *  如何合并？
 *  1 2 8   -1 2 3
 *  创建一个临时数组 temp
 *  1 -1 比较 -1 小  temp[-1]
 *  1 2  比较 1 小  temp[-1,1]
 *  2 2  比较 相等   temp[-1,1,2]
 *  2 3  比较 2 小    temp[-1,1,2,2]
 *  8 3  比较 3 小     temp[-1,1,2,2,3]
 *
 *  第一个有序队列 剩下 8 ，第二个有序队列 完全合并了
 *  8->temp[-1,1,2,2,3,8]   这时候temp是有序的
 * 2.3）知道合并成一个大的有序队列。
 * 2.4）将合并的复制到arr中
 *
 *          8 4   5 7   1 3   6 2
 * 归并-》   4 8   5 7   1 3   2 6
 * 归并-》   4 5 7 8   1 2 3 6
 * 归并-》   1 2 3 4 5 6 7 8
 *
 */
public class MergeSort {

    public static void main(String[] args) {

        int size=8000000;
        int[] testArr=new int[size];
        for(int i =0;i<testArr.length;i++){
            testArr[i]=(int)(Math.random()*size);
        }

        Instant start=Instant.now();
        separateSort(testArr,0,size-1,new int[testArr.length]);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); //15
//        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 分 合
     */
    public static void separateSort(int[] arr,int start,int end,int [] temp){
        if(start<end){
            int mid=(start+end)/2;
            // 往左边分
            separateSort(arr,start,mid,temp);
            // 往右边分
            separateSort(arr,mid+1,end,temp);
            // 合并 这里由于递归 最开始合并的是 第一个元素和第二个元素
            mergeSort(arr,start,mid,end,temp);
        }
    }

    /**
     * 合并
     * @param arr    要操作的数组
     * @param start  要合并的数据开始索引
     * @param mid    要合并的数据中间索引
     * @param end    要合并的数据结束索引
     */
    public static void mergeSort(int[] arr ,int start ,int mid ,int end ,int [] tempArr){

        // 临时数组 用来保存临时数据 如果在这里创建临时数组 那么这个时间会变长
//        int tempArr[] =new int[arr.length];
        int l=start;    // 要合并的 前面的有序列表的第一个索引
        int r=mid+1;    // 要合并的 后面的有序列表的第一个索引
        int t=0;        // tempArr的索引
        while (l<=mid&&r<=end){
            if(arr[l]<arr[r]){
                tempArr[t++]=arr[l++];
            }else {
                tempArr[t++]=arr[r++];
            }
        }
        // 这时候前后两个有序列表 一个已经移动完了
        while (l<=mid){
            tempArr[t++]=arr[l++];
        }
        while (r<=end){
            tempArr[t++]=arr[r++];
        }
        // 将临时数组中的元素复制到arr中
        t=0;
        int tempStart=start;
        while (tempStart<=end){
            arr[tempStart++]=tempArr[t++];
        }
    }
}
